package com.tsp;

import java.util.Scanner;

public class Dijkstra {

    public static void main(String[] args) {
        Dijkstra dijkstra = new Dijkstra();
        dijkstra.input();
        dijkstra.output();
    }
    private int[][] temp;       //邻接矩阵
    private int n;              //顶点个数
    private int s;              //出发点
    private int d;              //目标终点

    public Dijkstra() {
    }
    public void input(){        //初始化

        n = 9;
        s = 1;
        d = 9;

        temp = new int[n+1][n+1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n+1; j++) {
                temp[i][j] = Integer.MAX_VALUE;
            }
            temp[i][i] = 0;
        }
        temp[1][2] = 75;
        temp[1][3] = 118;
        temp[1][5] = 140;
        temp[3][4] = 111;
        temp[5][6] = 99;
        temp[5][9] = 300;
        temp[5][7] = 80;
        temp[6][9] = 211;
        temp[7][8] = 97;
        temp[8][9] = 101;

/*        Scanner scanner = new Scanner(System.in);
        int m;          //m条有向边
        n = scanner.nextInt();
        m = scanner.nextInt();
        s = scanner.nextInt();
        d = scanner.nextInt();

        //初始化邻接矩阵，权值为Integer.MAX_VALUE表示不可达
        temp = new int[n+1][n+1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n+1; j++) {
                temp[i][j] = Integer.MAX_VALUE;
            }
            temp[i][i] = 0;
        }

        int u_i,v_i,w_i;    //起点、终点、权值
        for (int i = 0; i < m; i++) {
            u_i = scanner.nextInt();
            v_i = scanner.nextInt();
            w_i = scanner.nextInt();

            temp[u_i][v_i] = w_i;

        }*/

    }

    public void output(){
        //temp[s][i]表示顶点s到顶点i的权值

        int weight[] = new int[n+1];     //记录顶点s到其余顶点的权值
        for (int i = 1; i < n + 1; i++) {
            weight[i] = temp[s][i];
        }

        boolean visited[] = new boolean[n+1];  //记录顶点s是否已访问其他顶点，false表示未访问
        visited[s] = true;

        boolean flag = true;       //标志顶点s是否已全部访问其他顶点
        int min_weight,min_peak = 0;//最小权值，对应的顶点
        while(true){
            min_weight = Integer.MAX_VALUE;
            for (int i = 1; i < n + 1; i++) {
                if(!visited[i]){    //当顶点s未访问顶点i时
                    flag = false;   //标志顶点s未全部访问完其他顶点

                    if(weight[i] < min_weight){
                        min_weight = weight[i];
                        min_peak = i;
                    }
                }

            }

            if(flag){       //若顶点s全部访问完其他顶点
                System.out.println(weight[d]);
                return;
            }

            for (int i = 1; i < n + 1; i++) {
                if(temp[min_peak][i] != Integer.MAX_VALUE){
                    weight[i] = Math.min(weight[i],temp[min_peak][i] + min_weight);
                }
            }
            visited[min_peak] = true;
            flag = true;

        }


    }
}
